/*
day246
2020.4.30
*/
#include<iostream> 
using namespace std;
struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};


class Solution {
public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
		if(find(root->left,p) && find(root->left,q))
		{
			return lowestCommonAncestor(root->left,p,q);
		}
		
		if(find(root->right,p) && find(root->right,q))
		{
			return lowestCommonAncestor(root->right,p,q);
		}
		
		return root;
    }
    
    bool find(TreeNode *root,TreeNode *target)
    {
    	if(!root)
    	{
    		return false;
		}
		
		if(root==target)
		{
			return true;
		}
		
		return find(root->left,target) || find(root->right,target);
	}
}; 

class Solution1 {
public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        if (!root ) return nullptr;
        TreeNode *left = lowestCommonAncestor(root->left, p, q);
        TreeNode *right = lowestCommonAncestor(root->right, p, q);
        if (root == p || root == q) return root;
        else if (left != nullptr && right != nullptr) return root;
        else if (left != nullptr) return left;
        else return right;

    }
};



class Solution2 {
public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
		bool l=find(root->left,p,q),r=find(root->right,p,q);
		
		if(l && r)
		{
			return root;
		}
		
		if(l && !r)
		{
			return lowestCommonAncestor(root->left,p,q);
		}
		
		return lowestCommonAncestor(root->right,p,q);
    }
    
    bool find(TreeNode *root,TreeNode *p,TreeNode *q)
    {
    	if(!root)
    	{
    		return false;
		}
		if(root==q || root==q)
		{
			return true;
		}
		return find(root->left,p,q) || find(root->right,p,q);
	}
}; 


int main()
{
	return 0;
}
